/*
题目链接 : https://leetcode.cn/problems/find-minimum-cost-to-remove-array-elements/description/
*/

//题解代码:

int dp[1001][1001];
class Solution {
public:
    int minCost(vector<int>& nums) {
        memset(dp,-1,sizeof(dp));
        int n = nums.size();
        if(n==1) return nums[0];
        else if(n==2) return max(nums[0],nums[1]);
        else if(n==3) return max(nums[0],max(nums[1],nums[2])) +min(nums[0],min(nums[1],nums[2]));

        //记忆化搜索
        auto dfs = [&](auto&& dfs,int i,int j)->int{
            if(dp[i][j] != -1) return dp[i][j];
            if(i==n-1) return max(nums[i],nums[j]);
            else if(i==n) return nums[j];
            int ret = INT_MAX;
            ret = max(nums[j],nums[i]) + dfs(dfs,i+2,i+1);
            ret = min(ret,max(nums[j],nums[i+1])+dfs(dfs,i+2,i));
            ret = min(ret,max(nums[i],nums[i+1])+dfs(dfs,i+2,j));
            dp[i][j] = ret;
            return ret;
        };

        int ans1 = max(nums[0],nums[1]) + dfs(dfs,3,2);
        int ans2 = max(nums[0],nums[2]) + dfs(dfs,3,1);
        int ans3 = max(nums[1],nums[2]) + dfs(dfs,3,0);
        return min(ans1,min(ans2,ans3));
    }
};
